// https://leetcode.cn/problems/arithmetic-slices/

// 算法思路总结：
// 1. 使用动态规划统计等差数列数量
// 2. dp[i]表示以i结尾的等差数列个数
// 3. 等差判断：nums[i]-nums[i-1] == nums[i-1]-nums[i-2]
// 4. 累加所有位置的等差数列数量
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int m = nums.size();
        if (m <= 2) return 0;

        int ret = 0;
        vector<int> dp(m, 0); 

        for (int i = 2 ; i < m ; i++)
        {
            int a = nums[i - 2], b = nums[i - 1], c = nums[i];
            dp[i] = (c - b == b - a ? dp[i - 1] + 1 : 0);
        }
        
        for (int i = 2 ; i < m ; i++)
            ret += dp[i];

        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4}, v2 = {0};
    Solution sol;

    cout << sol.numberOfArithmeticSlices(v1) << endl;
    cout << sol.numberOfArithmeticSlices(v2) << endl;

    return 0;
}